//
// Created by Dell on 2020/3/10.
//
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

void merge(int *a, int *b, int p, int q, int r) {
    int s = p, t = q + 1, k = p;
    while (s <= q && t <= r) {
        if (a[s] <= a[t])
            b[k++] = a[s++];
        else
            b[k++] = a[t++];
    }
    if (s == q + 1)
        for (int i = t; i <= r; i++)
            b[k++] = a[i];
    else
        for (int i = s; i <= q; i++)
            b[k++] = a[i];
    for (int i = p; i <= r; i++)
        a[i] = b[i];
}

//b为辅助数组
void bottomUpSort(int *a, int *b, int n) {
    int t = 1;
    while (t <= n) {
        int s = t;
        t = 2 * s;
        int i = 0;
        while (i + t <= n) {
            merge(a, b, i , i + s, i + t);
            i += t;
        }
        if (i + s < n)
            merge(a, b, i, i + s, n);
    }
}

int main(){
    srand((unsigned)time(nullptr));
    int a[8] = {0};
    for(int i = 0; i < 8; i++) {
        a[i] = rand() % 5000;
        cout << a[i] << " ";
    }
    cout << endl;
    int b[8] = {0};
    bottomUpSort(a, b, 7);
    for(int i = 0; i < 8; i++)
        cout << a[i] << " ";
}